import random
import math
import itertools
null = None

def random_tree(n_nodes, shuffle_nodes=True):
    """ tree其实就是无向无环连通图，0号是根节点 """
    if n_nodes <= 1:
        return []
    edges = [(random.randint(0, v-1), v) for v in range(1, n_nodes)]
    if shuffle_nodes:
        shuffle = random.sample(range(n_nodes), k=n_nodes)
        edges = [(shuffle[u], shuffle[v]) for (u, v) in edges]
    edges = [list(x) for x in edges]
    return edges


def random_directed_graph(n_nodes,
                          force_connected=False,
                          remove_parralel_edges=False):
    """ 有向图，可能有环 """
    n_edges = random.randint(0, math.perm(n_nodes, 2))
    edges = random.sample(list(itertools.permutations(
        range(n_nodes), 2)), n_edges)
    if force_connected:
        tree_edges = random_tree(n_nodes, shuffle_nodes=True)
        edges = list(set(edges).union(set(tree_edges)))
    if remove_parralel_edges:
        seen_edges = set()
        uniq_edges = []
        for u, v in edges:
            if (v, u) in seen_edges:
                continue
            seen_edges.add((u, v))
            uniq_edges.append((u, v))
        edges = uniq_edges
    edges = [list(x) for x in edges]
    return edges

def ramdom_directed_acyclic_graph(n_nodes, force_connected=False):
    """ 有向无环图 """
    n_edges = random.randint(0, math.comb(n_nodes, 2))
    edges = random.sample(list(
        itertools.combinations(range(n_nodes), 2)), n_edges)
    if force_connected:
        tree_edges = random_tree(n_nodes, shuffle_nodes=False)
        edges = list(set(edges).union(set(tree_edges)))

    shuffle = random.sample(range(n_nodes), k=n_nodes)
    edges = [(shuffle[u], shuffle[v]) for (u, v) in edges]
    edges = [list(x) for x in edges]
    return edges

def random_undirected_graph(n_nodes, force_connected=False):
    """ 无向图（可能有环） """
    n_edges = random.randint(0, math.comb(n_nodes, 2))
    edges = random.sample(list(
        itertools.combinations(range(n_nodes), 2)), n_edges)
    if force_connected:
        tree_edges = random_tree(n_nodes, shuffle_nodes=True)
        edges = list(set(edges).union(set(tree_edges)))
    edges = [list(x) for x in edges]
    return edges

def random_undirected_acyclic_graph(n_nodes, force_connected=False):
    """ 无向无环图 """
    edges = random_tree(n_nodes, shuffle_nodes=True)
    if not force_connected:
        edges = random.sample(edges, k=random.randint(0, len(edges)))
    edges = [list(x) for x in edges]
    return edges

def random_binary_tree(height, value_range, force_full=False):
    if height == 0:
        return []

    if force_full:
        n = random.randint(2**(height-1), 2**height-1)
        nodes = random.choices(value_range, k=n)
        return nodes

    mask = [1] * (2**height-1)
    pivot = random.randint(2**(height-1)-1, 2**height-2)
    def dfs(u):
        if u >= 2**(height-1)-1:
            if u == pivot:
                mask[u] = 1
            else:
                mask[u] = 1 - int(bool(random.randint(0, 4)))
            return mask[u]
        left = dfs(2*u+1)
        right = dfs(2*u+2)
        if left or right:
            mask[u] = 1
        else:
            mask[u] = random.randint(0, 1)
        return mask[u]
    dfs(0)

    values = random.choices(value_range, k=len(mask))
    nodes = [x if m else None for m, x in zip(mask, values)]
    while nodes and nodes[-1] is None:
        nodes.pop()
    return nodes

def visualize_graph(n, edges, directed=True, node_values=None,
                    edge_values=None, edge_colors=None):
    import graphviz
    if directed:
        g = graphviz.Digraph()
    else:
        g = graphviz.Graph()
    for i in range(n):
        content = str(i)
        if node_values:
            content += ':' + str(node_values[i])
        g.node(str(i), content)
    for e, (u, v) in enumerate(edges):
        edge_weight = ''
        if edge_values:
            edge_weight = str(edge_values[e])
        color = None if edge_colors is None else edge_colors[e]
        g.edge(str(u), str(v), edge_weight, color=color)
    return g

class TreeNode:
    id_ = 0
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
        self.id = TreeNode.id_
        TreeNode.id_ += 1
    def __repr__(self):
        repr_dict = {'id': self.id, 'val': self.val,
                     'left': self.left.id if self.left else None,
                     'right': self.right.id if self.right else None}
        return str(repr_dict)

def list_to_binary_tree(lst):
    TreeNode.id_ = 0
    if not lst:
        return None
    nodes = [TreeNode(val) if val is not None else None for i, val in enumerate(lst)]
    for i, node in enumerate(nodes):
        if node is not None:
            if 2 * i + 1 < len(nodes):
                node.left = nodes[2 * i + 1]
            if 2 * i + 2 < len(nodes):
                node.right = nodes[2 * i + 2]
    return nodes[0]


def leetcode_list_to_binary_tree(lst):
    TreeNode.id_ = 0
    if not lst:
        return None
    parents = {}
    root = TreeNode(lst[0])
    layer_nodes = [root]
    lst = lst[1:]
    while lst:
        pop_cnt = min(len(layer_nodes) * 2, len(lst))
        popped, lst = lst[:pop_cnt], lst[pop_cnt:]
        new_layer_nodes = []
        for i, x in enumerate(popped):
            if x is not None:
                node = TreeNode(x)
                parents[node] = (layer_nodes[i // 2], i % 2 == 0)
                new_layer_nodes.append(node)
        layer_nodes = new_layer_nodes
    for v, (u, is_left) in parents.items():
        if is_left:
            u.left = v
        else:
            u.right = v
    return root


def binary_tree_to_leetcode_list(root):
    from collections import deque
    path = []
    q = deque([root])
    while q:
        u = q.popleft()
        path.append(u)
        if u is None:
            continue
        q.append(u.left)
        q.append(u.right)
    while path and path[-1] is None:
        path.pop()
    return [u and u.val for u in path]


def visualize_binary_tree(tree: TreeNode):
    if tree is None:
        print('null tree')

    edges = []
    edge_colors = []
    nodes = []
    def get_edges():
        def dfs(u):
            nodes.append(u)
            if u.left:
                edges.append([u.id, u.left.id])
                edge_colors.append('red')
                dfs(u.left)
            if u.right:
                edges.append([u.id, u.right.id])
                edge_colors.append('black')
                dfs(u.right)
        dfs(tree)
    get_edges()

    nodes = sorted(nodes, key=lambda n: n.id)
    g = visualize_graph(len(nodes), edges, directed=True,
                        node_values=[n.val for n in nodes],
                        edge_colors=edge_colors)
    return g
